package tree;

import java.util.Scanner;

/**双亲表示法建立树,并输出任一种遍历序列检查所建树的正确性
 * */
public class ParentsTree<AnyType> {
	static int MaxTreeSize=100;
	static int count;
	PTNode[] node;
	
	//计算深度
	private int flag=0;
	private int depth=0;
	//存取每个树杈到达叶子节点的深度，用来求出最大的深度，及整棵树的深度
	/**初始化树
	 * */
	ParentsTree(){
		node = new PTNode[MaxTreeSize];
		count=-1;
	}
	
	/**添加节点
	 * */
	public void addPTNode(PTNode<AnyType> ptnode){
		++count;
		node[count]=ptnode;
	}
	/**输出树
	 * 
	 */
	public void printTree(){
		System.out.println("树的结构如下：");
		for(int i=0;i<=count;i++){
			System.out.println("下标： "+i+"  data:"+node[i].data+"  parent:"+node[i].parent);
		}
	}
	/**先跟遍历
	 * */
	public void preOrder(){
		System.out.println("树的先根遍历的结果为:");
		preOrder(0);
	}
	public void preOrder(int num){
		System.out.println("下标： "+num+"  data:"+node[num].data+"  parent:"+node[num].parent);
		//遍历剩余的元素找其孩子节点
		for(int j=num+1;j<=count;j++){
//			System.out.println("判断剩余结点"+j+"是否为"+num+"的孩子节点");
			if(node[j].parent==num){
				//开始递推
				preOrder(j);	
				//当递推的某一次的if条件不成立的时候，结束该递推，回归到上一步
//				System.out.println("结束到树杈"+j+"的所有访问"+",深度为:"+depth);
			}
			
		}
	}
	
	/**计算深度*/
	public int countDepth(){
		depth=1;
		for(int i=count;i>=0;i--){
			depth=countDepth(i);
			if(flag<=depth){
				flag=depth;
			}
			depth=1;
		}
		return flag;
	}
	public int countDepth(int num){
		if(num!=0){
			depth++;
			countDepth(node[num].parent);
		}
		return depth;
	}

	
	//测试函数
	public static void main(String[] args){
		ParentsTree<String> p=new ParentsTree<String>();
		Scanner in=new Scanner(System.in);
		System.out.println("请输入要创建的树的节点：（以'#'表示输入结束）");
		String data;
		int parent;
		while(!(data=in.next()).equals("#")){
			//此处必须每次都要new出来一个ptnode否则所有的节点都只会是同一个节点的值
			PTNode<String> ptnode=new PTNode<String>();
			ptnode.data=data;
			parent=in.nextInt();
			ptnode.parent=parent;
			p.addPTNode(ptnode);
		}
		
		//输出树的结构
		p.printTree();
		
		//输出创建的树
		p.preOrder();
		
		/*测试数据
A -1
B 0 
C 0
D 0
E 1	
F 1
G 2
H 3
I 3
J 3
	*/	
		
	}
}
class PTNode<AnyType>{
	AnyType data;
	int parent;
}
